// 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
// 你需要让组成和的完全平方数的个数最少。
// 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
// 输入：n = 13
// 输出：2
// 解释：13 = 4 + 9

// 思路，动态规划
// 完全平方数就是物品，凑成正整数n就是背包，解决凑成这个背包最少得物品
// 1. `dp[j]`, 和为j的完全平方数的最少数量
// 2. 递推公式,`dp[j] = Math.min(dp[j], dp[j - i * i] + 1)`
// 3. dp初始化，`dp[0] = 0`,其他初始化为最大值
// 4. 遍历顺序，如果求组合，外层物品，内层背包，求排列，外层背包，内层物品，该题，都可以
// 5. 举例
function numSquares(n) {
    let dp = new Array(n + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 0; i**2 <= n; i++) {
        for (let j = i * i; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - i**2] + 1)
        }        
    }
    return dp[n]
}

console.log(numSquares(13))